package Leetcode.sliding_window;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/3/26 14:41
 * @Description:
 * 学生分数的最小差值
 * 简单
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
 *
 * 从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
 *
 * 返回可能的 最小差值 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [90], k = 1
 * 输出：0
 * 解释：选出 1 名学生的分数，仅有 1 种方法：
 * - [90] 最高分和最低分之间的差值是 90 - 90 = 0
 * 可能的最小差值是 0
 * 示例 2：
 *
 * 输入：nums = [9,4,1,7], k = 2
 * 输出：2
 * 解释：选出 2 名学生的分数，有 6 种方法：
 * - [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
 * - [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
 * - [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
 * - [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
 * - [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
 * - [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
 * 可能的最小差值是 2
 *
 *
 * 提示：
 *
 * 1 <= k <= nums.length <= 1000
 * 0 <= nums[i] <= 105
 */

public class minimumDifference {
    public static void main(String[] args) {
        int[] nums = {87063,61094,44530,21297,95857,93551,9918};
        int k = 6;
        System.out.println(minimumDifference(nums, k));
    }

    /**
     * 这个k感觉对题意影响不大， 就是求两个成绩差值最小嘛，遍历就好了
     * 1.n*2遍历 两层循环遍历。懒得写了
     * 2.先sort  然后遍历一次，每次取相邻的两个数差值，取最小值
     *
     * emmm 看快题目了，k还是有影响的，k个成绩中取最高和最低分，然后取差值，不能单纯的求两个数的差值
     *
     * 推翻思路重来
     * 1.模拟题目要求，取出K个数，然后取最大最小求差值，重点在于怎么取这K个数呢，全排列有点。。。。复杂化了吧
     * 2.先排序，然后遍历一次，这次就不是取相邻的数了，相距K的两个数取差值
     * @param nums
     * @param k
     * @return
     */
    public static int minimumDifference(int[] nums, int k) {
        if (k == 1) {
            return 0;
        }
        int len = nums.length;
        int res = Integer.MAX_VALUE;
        Arrays.sort(nums);//从小到大
        for (int i = 0; i < len - k + 1; i++) {
            res = Math.min(res, nums[i + k - 1] - nums[i]);
        }
        return res;
    }
}
